package com.formula.datastructure.question.tree;

//Level order traversal, aka, 层次遍历
public class Quest05 {
    public static void main(String[] args) {
        Node05 root = new Node05(1);
        Node05 a1 = new Node05(42);
        Node05 a2 = new Node05(45);

        Node05 b1 = new Node05(39);
        Node05 b2 = new Node05(31);
        Node05 b3 = new Node05(35);
        Node05 b4 = new Node05(34);

        Node05 c1 = new Node05(21);

        /**
         *          1
         *      42          45
         *   39    31    35    34
         * 21
         */
        root.leftChild = a1;
        root.rightChild = a2;

        a1.leftChild = b1;
        a1.rightChild = b2;
        a2.leftChild = b3;
        a2.rightChild = b4;

        b3.rightChild = c1;

        Tree05 tree = new Tree05(root);
        tree.levelOrder();
    }
}

class Tree05 {
    private Node05 root;
    private int front;
    private int rear;
    private Node05[] queue;

    public Tree05(Node05 root) {
        this.root = root;
    }

    public int getSize() {
        int count = 0;
        if (root != null) {
            return root.getSize(count);
        }
        return 0;
    }

    public void levelOrder() {

        //queue = new Node05[getSize()];
        queue = new Node05[100];
        front = 0;
        rear = 0;
        if (root != null) {
            queue[rear++] = root;
            while (front < rear) {
                Node05 current = queue[front++];
                System.out.println(current.data);
                if (current.leftChild != null) {
                    queue[rear++] = current.leftChild;
                }
                if (current.rightChild != null) {
                    queue[rear++] = current.rightChild;
                }
            }
        }
    }
}

class Node05 {
    public Integer data;
    public Node05 leftChild;
    public Node05 rightChild;
    private int size;

    public Node05(Integer data) {
        this.data = data;
    }

    public int getSize(int count) {
        ++count;
        if (leftChild != null) {
            count = leftChild.getSize(count);
        }
        if (rightChild != null) {
            count = rightChild.getSize(count);
        }
        return count;
    }

}



